/**
 * @file demo1.c
 * @author WRS (1352509846@qq.com)
 * @brief 两数之和
 * 给定一个整数数组nums和一个整数目标值target，请在该数组中找出和目标值
 * @version 0.1
 * @date 2021-09-05
 * 
 * @copyright Copyright (c) 2021
 * 
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/**
 * Note: The returned array must be malloced, assume caller calls free().
 * 暴力解法
 */
// int* twoSum(int* nums, int numsSize, int target, int* returnSize)
// {
//     for(int i=0;i<numsSize;i++)
//     {
//         for(int j=i+1;j<numsSize;j++)
//         {
//             if(nums[i]+nums[j]==target)
//             {
//                 int *ret = malloc(sizeof(int)*2);
//                 ret[0] = i;
//                 ret[1] = j;
//                 *returnSize = 2;
//                 return ret;
//             }
//         }
//     }
//     *returnSize = 0;
//     return NULL;
// }

/**
 * @brief 哈希表方法
 */

struct hashTable {
    int key;
    int val;
    UT_hash_handle hh;
};

struct hashTable* hashtable;

struct hashTable* find(int ikey) {
    struct hashTable* tmp;
    HASH_FIND_INT(hashtable, &ikey, tmp);
    return tmp;
}

void insert(int ikey, int ival) {
    struct hashTable* it = find(ikey);
    if (it == NULL) {
        struct hashTable* tmp = malloc(sizeof(struct hashTable));
        tmp->key = ikey, tmp->val = ival;
        HASH_ADD_INT(hashtable, ikey, tmp);
    } else {
        it->val = ival;
    }
}

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    hashtable = NULL;
    for (int i = 0; i < numsSize; i++) {
        struct hashTable* it = find(target - nums[i]);
        if (it != NULL) {
            int* ret = malloc(sizeof(int) * 2);
            ret[0] = it->val, ret[1] = i;
            *returnSize = 2;
            return ret;
        }
        insert(nums[i], i);
    }
    *returnSize = 0;
    return NULL;
}
int main(int argc, const char *argv[])
{
	int *tab = NULL;
    int returnSize = 0;
	int array[]={1,2,3,4,5,6};

	printf("leetcode第一题：两数之和\n");
	
	tab = twoSum(array,sizeof(array)/sizeof(array[0]),6,&returnSize);

    if(returnSize!=0)
	    printf("%d,%d\n",tab[0],tab[1]);
    else
        printf("没有\n");
	return 0;
}


